#include<bits/stdc++.h>
//#define int long long
#define re register
#define rep(i,a,b) for(int i(a);i<=(b);++i)
#define req(i,a,b) for(int i(a);i>=(b);--i)
using namespace std;
#ifdef ONLINE_JUDGE
char buf[(1<<21)+5],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
template<typename T> inline int read(T &num){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return num=f?-x:x;
}
inline int Read()
{
	re int x=0,f=0;re char ch=getchar();
	while(!isdigit(ch)) f|=ch=='-',ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
template<typename T> inline void write(T num)
{
	num=num<0?putchar('-'),-num:num;
	num>9?write(num/10),0:0;
	putchar(num%10+48);
}
template<typename T> inline void writeln(T num)
{
	write(num);
	putchar('\n');
}
///////////////////////////////////////////////////////////////
int n,t;
string fnow,fpre,fppr;
string p;
void getf()
{
	if(n==1) return fnow="0",void();
	if(n==2) return fnow="1",void();
	fppr="0",fpre="1",fnow="10";
	rep(i,4,n)
	{
		fppr=fpre;
		fpre=fnow;
		fnow+=fppr;
	}
}
signed main()
{
	freopen("brotherhood.in","r",stdin);
	freopen("brotherhood.out","w",stdout);
	read(n);read(t);
	getf();
	while(t--)
	{
		cin>>p;
		int pos=-1,ans=0;
		while((pos=fnow.find(p,pos+1))!=-1) ++ans;
		writeln(ans);
	}
	return 0;
}

